# -*-coding = utf-8 -*-

# @Time: 2021/4/3 23:29
# @Author: bistro
# @File: p1143.py
# @Software: PyCharm
from typing import List


class Solution:
    # 动态规划
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        l1, l2 = len(text1), len(text2)
        dp = [[0 for i in range(l2 + 1)] for j in range(l1 + 1)]
        for p in range(1, l1 + 1):
            for q in range(1, l2 + 1):
                if text1[p - 1] == text2[q - 1]:
                    dp[p][q] = dp[p - 1][q - 1] + 1
                else:
                    dp[p][q] = max(dp[p - 1][q], dp[p][q - 1])
        return dp[l1][l2]


"""
测试用例
s = Solution()
res = s.longestCommonSubsequence("apmjghexybyrgzczy", "ahafcdqbgncrcbihkd")
print(res)
"""


# 超时 时间：大于 O(2**n)
# 递归实现 超时
# "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
# "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
def longestCommonSubsequence(text1: str, text2: str) -> int:
    l1 = len(text1)
    l2 = len(text2)
    if l1 == 0 or l2 == 0:
        return 0
    if text1[-1] == text2[-1]:
        return longestCommonSubsequence(text1[:l1 - 1], text2[:l2 - 1]) + 1
    else:
        t1 = longestCommonSubsequence(text1[:l1 - 1], text2[:l2])
        t2 = longestCommonSubsequence(text1[:l1], text2[:l2 - 1])
        return t1 if t1 > t2 else t2


# 二进制枚举 超时
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    tl1 = self.subsetsWithDup(list(text1))
    tl2 = self.subsetsWithDup(list(text2))
    intersection = list(set(tl1).intersection(set(tl2)))
    return len(max(intersection, key=len))


def subsetsWithDup(self, nums: List[str]) -> List[str]:
    results = []
    for i in range(0, 1 << len(nums)):
        new_str = ""
        for j in range(0, len(nums)):
            if i & (1 << j):
                new_str += nums[j]
        results.append(new_str)
    return results

